// 递归关系
/*
eg1:
1 3 5 7 9 11 13 ...
递归关系： f(n) = f(n-1) + 2
出口: f(1) = 1

int f(int n)
{
    if(n==1)
    {
        return 1;
    }
    else
    {
        return f(n-1)+2;
    }
    
}

eg2:
Fibonacci: 1 1 2 3 5 8 13 21 ...

int f(int n)
{
    if(n==1)
    {
        return 1;
    }
    else if(n==2)
    {
        return 1;
    }
    else
    {
        return f(n-1)+f(n-2);
    }
    
}

eg3:
1+2+3+4+...+100
递推关系：f(n) = f(n-1) +n
出口：f(1)=1

int sum(int n)
{
    if(n==1)
    {
        return 1;
    }
    else
    {
        reutrn (sum(n-1)+n);
    }
    
}

eg4:
int arr[] = {1, 7, 8, 6, 4, 7, 3}
求前n项之和

递推关系： sum(arr, n) = sum(arr, n-1) + arr[n]
出口： sum(arr, 0) = arr[0]

int sum(int arr[], int n)
{
    if(n==0)
    {
        return arr[0];
    }
    else
    {
        return sum(arr, n-1)+arr[n];
    }
    
}

eg5:
arr[]={7,4,8,6,3,2,9,11,5} 求数组里面的最大值

max(arr, n)

递归关系： 
if max(arr, n-1) > arr[n]
    return max(arr, n-1)
else
    return arr[n]

出口：if(n==0)
        return arr[0];

*/

// 二叉树01

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
  int data;
  struct node *left;
  struct node *right;
} Node;

// 前序遍历
void preorder(Node *node)
{
  if (node != NULL)
  {
    // 出口
    printf("%d\n", node->data);
    // 递归关系
    preorder(node->left);
    preorder(node->right);
  }
}

// 中序遍历
void inorder(Node *node)
{
  if (node != NULL)
  {
    // 递归关系
    inorder(node->left);
    // 出口
    printf("%d\n", node->data);
    // 递归关系
    inorder(node->right);
  }
}

// 后序遍历
void postorder(Node *node)
{
  if (node != NULL)
  {
    postorder(node->left);
    postorder(node->right);
    printf("%d\n", node->data);
  }
}

int main()
{
  Node n1;
  Node n2;
  Node n3;
  Node n4;

  n1.data = 5;
  n2.data = 6;
  n3.data = 7;
  n4.data = 8;

  n1.left = &n2;
  n1.right = &n3;
  n2.left = &n4;
  n2.right = NULL;
  n3.left = NULL;
  n3.right = NULL;
  n4.left = NULL;
  n4.right = NULL;

  inorder(&n1);
}

// 二叉树02: 二叉搜索树
